//实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 
//
// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 
//
// 必须 原地 修改，只允许使用额外常数空间。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[1,3,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[1,2,3]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,1,5]
//输出：[1,5,1]
// 
//
// 示例 4： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 100 
// 0 <= nums[i] <= 100 
// 
// Related Topics 数组 
// 👍 1179 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;

// 【 1，2，3，4，7，6，5】
public class NextPermutation {
    public static void main(String[] args) {
        Solution solution = new NextPermutation().new Solution();
        int[] n = new int[]{1, 2, 3};
        solution.nextPermutation(n);
        System.out.println(Arrays.toString(n));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 对于从右到左升序序列，无论如何交换，结果都是变小
    // 因此要找打破从右到左升序的位置，即峰值左边元素，下标记为leftFirst
    // 为了保证变化幅度最小，因此要找到升序序列中大于nums[leftFirst]且最接近它的，记下标为rightFirst
    class Solution {
        public void nextPermutation(int[] nums) {
            int min = Integer.MIN_VALUE;
            int leftFirst = 0;
            int rightFirst = 0;
            // 找到leftFirst
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] > min) {
                    min = nums[i];
                } else {
                    leftFirst = i;
                    break;
                }
            }
            //找到rightFirst
            for (int i = nums.length - 1; i > leftFirst; i--) {
                if (nums[i] > nums[leftFirst]) {
                    rightFirst = i;
                    break;
                }
            }
            // 如果整个nums都是右到左升序，那么直接重排
            if (rightFirst == leftFirst) {
                Arrays.sort(nums);
                return;
            }
            // 否则交换，得到下一个排列
            int temp = nums[rightFirst];
            nums[rightFirst] = nums[leftFirst];
            nums[leftFirst] = temp;
            return;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}